<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Syntax
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora105.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora107.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Syntax</H2><A NAME="sec-BNF"></A>
<A NAME="@concepts229"></A>
Thanks to lexical analysis, we can split up input streams into more
structured units: lexical units. We still need to know how to assemble
these units so that they amount to syntactically correct sentences in
a given language. The syntactic assembly rules are defined by
grammar rules. This formalism was originally developed in the
field of linguistics, and has proven immensely useful to
language-theoretical mathematicians and computer scientists in that
field. We have already seen on page <A HREF="book-ora058.html#subsec-gram-basic">??</A> an
instance of a grammar for the Basic language. We will resume this
example to introduce the basic concepts for grammars.<BR>
<BR>
<A NAME="toc136"></A>
<H3> Grammar</H3>
<A NAME="@concepts230"></A>
<A NAME="@concepts231"></A>
<A NAME="@concepts232"></A>
<A NAME="@concepts233"></A>Formally, a grammar is made up of four elements:
<A NAME="@concepts234"></A>
<A NAME="@concepts235"></A>
<OL type=1>
<LI> a set of symbols called terminals. Such symbols
represent the lexical units of the language. In Basic, 
the lexical units (terminals) are: the
operator- and arithmetical and logical relation-symbols (<TT>+</TT>, <TT>&amp;</TT>, <TT>&lt;</TT>, <TT>&lt;=</TT>, ..), the keywords of the language (<TT>GOTO</TT>, <TT>PRINT</TT>, <TT>IF</TT>, <TT>THEN</TT>, ..), integers (<I>integer</I>
units) and variables (<I>variable</I> units).<BR>
<BR>

<LI> A set of symbols called non-terminals. Such symbols
stand for syntactic terms of the language. For example, a
Basic program is composed of lines (and thus we have the term <FONT COLOR=navy>Line</FONT>), a line may contain and <FONT COLOR=navy>Expression</FONT>, etc.<BR>
<BR>

<LI> A set of so-called production rules. These describe how
terminal and non-terminals symbols may be combined to produce a syntactic
term. A Basic line is made up of a number followed by an
instruction. This is expressed in the following rule:
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>Line</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><I>integer</I> <FONT COLOR=navy>Instruction</FONT></TD>
</TR></TABLE>
</DIV>
For any given term, there may be several alternative ways to form that
term. We separate the alternatives with the symbol | as in
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>Instruction</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><TT>LET</TT> <I>variable</I> <TT>=</TT> <FONT COLOR=navy>Expression</FONT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>GOTO</TT> <I>integer</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>PRINT</TT> <FONT COLOR=navy>Expression</FONT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>etc.</TD>
</TR></TABLE>
</DIV><BR>

<LI> Finally, we designate a particular non-terminal as the
start symbol. The start symbol identifies a complete
translation unit (program) in our language, and the corresponding
production rule is used as the starting point for parsing.
</OL><A NAME="toc137"></A>
<H3> Production and Recognition</H3><A NAME="subsec-prod"></A>
Production rules allow recognition that a sequence of
lexemes belongs to a particular language.<BR>
<BR>
Let's consider, for instance, a simple language for arithmetic
expressions: 
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>Exp</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><I>integer</I></TD>
<TD  ALIGN=right NOWRAP>(R1)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Exp</FONT> <TT>+</TT> <FONT COLOR=navy>Exp</FONT></TD>
<TD  ALIGN=right NOWRAP>(R2)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Exp</FONT> <TT>*</TT> <FONT COLOR=navy>Exp</FONT></TD>
<TD  ALIGN=right NOWRAP>(R3)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>(</TT> <FONT COLOR=navy>Exp</FONT> <TT>)</TT></TD>
<TD  ALIGN=right NOWRAP>(R4)</TD>
</TR></TABLE>
</DIV><BR>
where (R1) (R2) (R3) and (R4) are the names given to our rules. After
lexical analysis, the expression <CODE>1*(2+3)</CODE> becomes the sequence
of lexemes:
<DIV ALIGN=center>
<I>integer</I> <TT>*</TT> <TT>(</TT> <I>integer</I> <TT>+</TT> <I>integer</I> <TT>)</TT>
</DIV><BR>
To analyze this sentence and recognize that it really belongs to the
language of arithmetic expressions, we are going to use the rules
from right to left: if a subexpression matches the right-side member
of a rule, we replace it with the corresponding left-side member and
we re-run the process until reducing the expression to the
non-terminal <I>start</I> (here <FONT COLOR=navy>Exp</FONT>). Here are the stages of such an
analysis<A NAME="text27" HREF="book-ora111.html#note27"><SUP><FONT SIZE=2>4</FONT></SUP></A>:
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><U><I>integer</I></U> <TT>*</TT> <TT>(</TT> <I>integer</I> <TT>+</TT> <I>integer</I> <TT>)</TT></TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>1)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Exp</FONT> <TT>*</TT> <TT>(</TT> <U><I>integer</I></U> <TT>+</TT> <I>integer</I> <TT>)</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>1)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Exp</FONT> <TT>*</TT> <TT>(</TT> <FONT COLOR=navy>Exp</FONT> <TT>+</TT> <U><I>integer</I></U> <TT>)</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>1)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Exp</FONT> <TT>*</TT> <TT>(</TT> <U><FONT COLOR=navy>Exp</FONT></U><U> </U><U><TT>+</TT></U><U> </U><U><FONT COLOR=navy>Exp</FONT></U> <TT>)</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>2)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Exp</FONT> <TT>*</TT> <U><TT>(</TT></U><U> </U><U><FONT COLOR=navy>Exp</FONT></U><U> </U><U><TT>)</TT></U></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>4)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><U><FONT COLOR=navy>Exp</FONT></U><U> </U><U><TT>*</TT></U><U> </U><U><FONT COLOR=navy>Exp</FONT></U></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>3)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Exp</FONT></TD>
</TR></TABLE>
</DIV><BR>
Starting from the last line containing only <FONT COLOR=navy>Exp</FONT> and following
the arrows upwards we read how our expression could be produced from
the start rule <FONT COLOR=navy>Exp</FONT>: therefore it is a well-formed sentence of
the language defined by the grammar.<BR>
<BR>
The translation of grammars into programs capable of recognizing that
a sequence of lexemes belongs to the language defined by a grammar is
a much more complex problem than that of using regular
expressions. Indeed, a mathematical result tells us that all sets (of
words) defined by means of a regular expression formalism can also be
defined by another formalism: deterministic finite
automata. And these latter are easy to explain as programs taking as
input a sequence of characters. We do not have a similar result for
the case of generic grammars. However, we have weaker results
establishing the equivalence between certain classes of grammars and
somewhat richer automata: pushdown automata. We do not want
to enter into the details of such results, nor give an exact
definition of what an automaton is. Still, we need to identify 
a class of grammars that may be used with parser-generating tools or
parsed directly.<BR>
<BR>
<A NAME="toc138"></A>
<H3> Top-down Parsing</H3>
<A NAME="@concepts236"></A>
<A NAME="@concepts237"></A>
<A NAME="@concepts238"></A>The analysis of the expresion <CODE>1*(2+3)</CODE> introduced in the
previous paragraph is not unique: it could also have started by
reducing <I>integers</I> from right to left, which would have permitted
rule (R2) to reduce <CODE>2+3</CODE> from the beginning instead. These two
ways to proceed constitute two types of analysis: top-down parsing
(right-to-left) and bottom-up parsing (left-to-right). The latter is
easily realizable with lexeme streams using module
<TT>Stream</TT>. Bottom-up parsing is that carried-out by the
<TT>ocamlyacc</TT> tool. It uses an explicit stack mechanism like the
one already described for the parsing of Basic programs. The choice
of parsing type is significant, as top-down analysis may or
may not be possible given the form of the grammar used to specify the
language.<BR>
<BR>

<H4> A Simple Case</H4>
The canonical example for top-down parsing is the prefix notation of
arithmetic expressions defined by:
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>Expr</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><I>integer</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>+</TT> <FONT COLOR=navy>Expr</FONT> <FONT COLOR=navy>Expr</FONT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>*</TT> <FONT COLOR=navy>Expr</FONT> <FONT COLOR=navy>Expr</FONT></TD>
</TR></TABLE>
</DIV><BR>
In this case, knowing the first lexeme is enough to decide which
production rule can be used. This immediate predictability 
obviates managing the parse stack explicitly by instead using the
stack of recursive calls in the parser. Therefore, it is
very easy to write a program implementing top-down analysis using the
features in modules <TT>Genlex</TT> and
<TT>Stream</TT>. Function <TT>infix_of</TT> is an example; it takes a
prefix expression and returns its equivalent infix expression.<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>lexer<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ll<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Genlex.make_lexer<CODE> </CODE><CODE>[</CODE><CODE>"+"</CODE>;<CODE>"*"</CODE><CODE>]</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><CODE> </CODE>ll<CODE> </CODE><TT>(</TT>Stream.of_string<CODE> </CODE>s<TT>)</TT><CODE> </CODE>;;<BR><CODE>val lexer : string -&gt; Genlex.token Stream.t = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>stream_parse<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>s<CODE> </CODE><B>with</B><CODE> </CODE><B>parser</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE>'Genlex<CODE>.</CODE>Ident<CODE> </CODE>x<CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>x<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE>'Genlex<CODE>.</CODE>Int<CODE> </CODE>n<CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>string_of_int<CODE> </CODE>n<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE>'Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE>"+"</CODE>;<CODE> </CODE>e1<CODE>=</CODE>stream_parse;<CODE> </CODE>e2<CODE>=</CODE>stream_parse<CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"("</CODE><CODE>^</CODE>e1<CODE>^</CODE><CODE>"+"</CODE><CODE>^</CODE>e2<CODE>^</CODE><CODE>")"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE>'Genlex<CODE>.</CODE>Kwd<CODE> </CODE><CODE>"*"</CODE>;<CODE> </CODE>e1<CODE>=</CODE>stream_parse;<CODE> </CODE>e2<CODE>=</CODE>stream_parse<CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"("</CODE><CODE>^</CODE>e1<CODE>^</CODE><CODE>"*"</CODE><CODE>^</CODE>e2<CODE>^</CODE><CODE>")"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>failwith<CODE> </CODE><CODE>"Parse error"</CODE><BR><CODE> </CODE>;;<BR><CODE>val stream_parse : Genlex.token Stream.t -&gt; string = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>infix_of<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE>stream_parse<CODE> </CODE><TT>(</TT>lexer<CODE> </CODE>s<TT>)</TT><CODE> </CODE>;;<CODE> </CODE><BR><CODE>val infix_of : string -&gt; string = &lt;fun&gt;</CODE><BR># infix_of<CODE> </CODE><CODE>"* +3 11 22"</CODE>;;<BR><CODE>- : string = "((3+11)*22)"</CODE><BR>

</PRE>
<BR>
<BR>
One has to be careful, because this parser is rather unforgiving.
It is advisable to
introduce a blank between lexical units in the input string
systematically.


<PRE><BR># infix_of<CODE> </CODE><CODE>"*+3 11 22"</CODE>;;<BR><CODE>- : string = "*+"</CODE><BR>

</PRE>
<BR>
<BR>

<H4> A Less Simple Case</H4>
Parsing using streams is predictive. It imposes two conditions on
grammars. 
<OL type=1>
<LI>
 There must be no left-recursive rules in the grammar. A
rule is left-recursive when a right-hand expression starts with a
non-terminal which is the left-hand member of the expression, as in
<FONT COLOR=navy>Exp</FONT> ::= <FONT COLOR=navy>Exp</FONT> <TT>+</TT> <FONT COLOR=navy>Exp</FONT>;

<LI> No two rules may start with the same expression.
</OL>The usual grammar for arithmetical expressions on page
<A HREF="book-ora106.html#subsec-prod">??</A> is not directly suitable for top-down analysis:
it does not satisfy any of the above-stated criteria. To be able to
use top-down parsing, we must reformulate the grammar so as to
suppress left-recursion and non-determinism in the rules. For
arithmetic expressions, we may use, for instance:
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>Expr</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Atom</FONT> <FONT COLOR=navy>NextExpr</FONT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>NextExpr</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><TT>+</TT> <FONT COLOR=navy>Atom</FONT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>-</TT> <FONT COLOR=navy>Atom</FONT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>*</TT> <FONT COLOR=navy>Atom</FONT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>/</TT> <FONT COLOR=navy>Atom</FONT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT FACE=symbol>e</FONT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>Atom</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><I>integer</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>(</TT> <FONT COLOR=navy>Expr</FONT> <TT>)</TT></TD>
</TR></TABLE>
</DIV><BR>
Note that the use of the empty word <FONT FACE=symbol>e</FONT> in the definition of 
<FONT COLOR=navy>NextExpr</FONT> is compulsory if we want a single integer to be an
expression.<BR>
<BR>
Our grammar allows the implementation of the following parser which is
a simple translation of the production rules. This parser produces the
abstract syntax tree of arithmetic expressions.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>rest<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>parser</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"+"</CODE>;<CODE> </CODE>e2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>atom<CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>Some<CODE> </CODE><TT>(</TT>PLUS<CODE>,</CODE>e2<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"-"</CODE>;<CODE> </CODE>e2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>atom<CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>Some<CODE> </CODE><TT>(</TT>MINUS<CODE>,</CODE>e2<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"*"</CODE>;<CODE> </CODE>e2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>atom<CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>Some<CODE> </CODE><TT>(</TT>MULT<CODE>,</CODE>e2<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"/"</CODE>;<CODE> </CODE>e2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>atom<CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>Some<CODE> </CODE><TT>(</TT>DIV<CODE>,</CODE>e2<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>None<BR><CODE> </CODE><B>and</B><CODE> </CODE>atom<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>parser</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lint<CODE> </CODE>i<CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>ExpInt<CODE> </CODE>i<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"("</CODE>;<CODE> </CODE>e<CODE> </CODE><CODE>=</CODE><CODE> </CODE>expr<CODE> </CODE>;<CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>")"</CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>e<BR><CODE> </CODE><B>and</B><CODE> </CODE>expr<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>s<CODE> </CODE><B>with</B><CODE> </CODE><B>parser</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>e1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>atom<CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>rest<CODE> </CODE>s<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>None<CODE> </CODE>-&gt;<CODE> </CODE>e1<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Some<CODE> </CODE><TT>(</TT>op<CODE>,</CODE>e2<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>ExpBin<TT>(</TT>e1<CODE>,</CODE>op<CODE>,</CODE>e2<TT>)</TT><CODE> </CODE>;;<BR><CODE>val rest : lexeme Stream.t -&gt; (bin_op * expression) option = &lt;fun&gt;</CODE><BR><CODE>val atom : lexeme Stream.t -&gt; expression = &lt;fun&gt;</CODE><BR><CODE>val expr : lexeme Stream.t -&gt; expression = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The problem with using top-down parsing is that it forces us to
use a grammar which is very restricted in its form. Moreover, when the
object language is naturally described with a left-recursive grammar 
(as in the case of infix expressions) it is not always trivial to find
an equivalent grammar (i.e. one defining the same language) that
satisfies the requirements of top-down parsing. This is the reason why
tools such as <TT>yacc</TT> and <TT>ocamlyacc</TT> use a bottom-up
parsing mechanism which allows the definition of more natural-looking
grammars. We will see, however, that not everything is possible
with them, either.<BR>
<BR>
<A NAME="toc139"></A>
<H3> Bottom-up Parsing</H3>
<A NAME="@concepts239"></A>
On page <A HREF="book-ora058.html#basic-synt0">??</A>, we introduced intuitively the
actions of bottom-up parsing: shift and
reduce. With each of these actions the state of the stack is
modified. We can deduce from this sequence of actions the grammar
rules, provided the grammar allows it, as in the case of top-down
parsing. Here, also, the difficulty lies in the non-determinism of
the rules which prevents choosing between shifting and reducing. We
are going to illustrate the inner workings of bottom-up parsing and its
failures by considering those pervasive arithmetic expressions in
postfix and prefix notation.<BR>
<BR>

<H5> The Good News</H5>
The simplified grammar for postfix arithmetic expressions is:
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>Expr</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><I>integer</I></TD>
<TD  ALIGN=right NOWRAP>(R1)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Expr</FONT> <FONT COLOR=navy>Expr</FONT> <TT>+</TT></TD>
<TD  ALIGN=right NOWRAP>(R2)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Expr</FONT> <FONT COLOR=navy>Expr</FONT> <TT>*</TT></TD>
<TD  ALIGN=right NOWRAP>(R3)</TD>
</TR></TABLE>
</DIV><BR>
This grammar is dual to that of prefix expressions: it is necessary
to wait until the end of each analysis to know which rule
has been used, but then one knows exactly what to
do. In fact, the bottom-up analysis of such expressions resembles
quite closely a stack-based evaluation mechanism. Instead of pushing
the results of each calculation, we simply push the grammar
symbols. The idea is to start with an empty stack, then obtain a stack
which contains only the start symbol once the input is used
up. The modifications to the stack are the following: when we shift,
we push the present non-terminal; if we may reduce, it is because the
first elements in the stack match the right-hand member of a rule (in
reverse order), in which case we replace these elements by the
corresponding left-hand non-terminal.<BR>
<BR>
Figure <A HREF="book-ora106.html#fig-anasc">11.2</A> illustrates how bottom-up parsing processes
expression: <TT>1 2 + 3 * 4 +</TT>.
The input lexical unit is underlined. The end of input is noted with a
<TT>$</TT> sign.
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD  ALIGN=center NOWRAP><FONT COLOR=navy>Action</FONT></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Input</FONT></TD>
<TD  ALIGN=right NOWRAP><FONT COLOR=navy>Stack</FONT></TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>1</U></TT><TT>2+3*4+$</TT></TD>
<TD  ALIGN=right NOWRAP>[]</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP COLSPAN=2>Shift</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>2</U></TT><TT>+3*4+$</TT></TD>
<TD  ALIGN=right NOWRAP>[<TT>1</TT>]</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP COLSPAN=2>Reduce (R1)</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>2</U></TT><TT>+3*4+$</TT></TD>
<TD  ALIGN=right NOWRAP>[<FONT COLOR=navy>Expr</FONT>]</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>Shift</TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>+</U></TT><TT>3*4+$</TT></TD>
<TD  ALIGN=right NOWRAP>[<TT>2</TT><FONT COLOR=navy>Expr</FONT>]</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP COLSPAN=2>Reduce (R1)</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>+</U></TT><TT>3*4+$</TT></TD>
<TD  ALIGN=right NOWRAP>[<FONT COLOR=navy>Expr</FONT> <FONT COLOR=navy>Expr</FONT>]</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP COLSPAN=2>Shift, Reduce (R2)</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>3</U></TT><TT>*4+$</TT></TD>
<TD  ALIGN=right NOWRAP>[<FONT COLOR=navy>Expr</FONT>]</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP COLSPAN=2>Shift, Reduce (R1)</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>*</U></TT><TT>4+$</TT></TD>
<TD  ALIGN=right NOWRAP>[<FONT COLOR=navy>Expr</FONT> <FONT COLOR=navy>Expr</FONT>]</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP COLSPAN=2>Shift, Reduce (R3)</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>4</U></TT><TT>+$</TT></TD>
<TD  ALIGN=right NOWRAP>[<FONT COLOR=navy>Expr</FONT>]</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP COLSPAN=2>Shift, Reduce (R1)</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>+</U></TT><TT>$</TT></TD>
<TD  ALIGN=right NOWRAP>[<FONT COLOR=navy>Expr</FONT> <FONT COLOR=navy>Expr</FONT>]</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP COLSPAN=2>Shift, Reduce (R2)</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><TT><U>$</U></TT></TD>
<TD  ALIGN=right NOWRAP>[<FONT COLOR=navy>Expr</FONT>]</TD>
</TR></TABLE>
</DIV>
<BR>
<DIV ALIGN=center>Figure 11.2: Bottom-up parsing example<A NAME="fig-anasc"></A>.</DIV><BR>

<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<H5> The Bad News</H5> 
<A NAME="@concepts240"></A>
<A NAME="@concepts241"></A>
The difficulty of migrating the grammar into the recognition program
is determining which type of action to apply. We will illustrate this
difficulty with three examples which generate three types of
indeterminacy.<BR>
<BR>
The first example is a grammar for expressions using only addition:
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>E0</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><I>integer</I></TD>
<TD  ALIGN=right NOWRAP>(R1)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E0</FONT> <TT>+</TT> <FONT COLOR=navy>E0</FONT></TD>
<TD  ALIGN=right NOWRAP>(R2)</TD>
</TR></TABLE>
</DIV>
The indeterminacy in this grammar stems from rule (R2). Let's suppose
the following situation:
<DIV ALIGN=center>
<TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD  ALIGN=center NOWRAP><FONT COLOR=navy>Action</FONT></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Input</FONT></TD>
<TD  ALIGN=right NOWRAP><FONT COLOR=navy>Stack</FONT></TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>:</TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><U><TT>+</TT></U>...</TD>
<TD  ALIGN=right NOWRAP>[<FONT COLOR=navy>E0</FONT> <TT>+</TT> <FONT COLOR=navy>E0</FONT> ...]</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>:</TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR></TABLE>
</DIV><BR>
<A NAME="@concepts242"></A>
In such a case, it is impossible to determine whether we have to shift
and push the <TT>+</TT> or to reduce using (R2) both <FONT COLOR=navy>E0</FONT>'s and the
<TT>+</TT> in the stack. We are in the presence of a shift-reduce
conflict. This is because expression <I>integer</I> <TT>+</TT>
<I>integer</I> <TT>+</TT> <I>integer</I> can be produced in two ways by
right-derivation.<BR>
<BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP>First way:</TD>
<TD  ALIGN=right NOWRAP><FONT COLOR=navy>E0</FONT></TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>2)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E0</FONT> <TT>+</TT> <U><FONT COLOR=navy>E0</FONT></U></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>1)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><U><FONT COLOR=navy>E0</FONT></U> <TT>+</TT> <I>integer</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>2)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E0</FONT> <TT>+</TT> <U><FONT COLOR=navy>E0</FONT></U> <TT>+</TT> <I>integer</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>etc.</TD>
</TR></TABLE><BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP>Second way:</TD>
<TD  ALIGN=right NOWRAP><FONT COLOR=navy>E0</FONT></TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>2)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E0</FONT> <TT>+</TT> <U><FONT COLOR=navy>E0</FONT></U></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>2)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E0</FONT> <TT>+</TT> <FONT COLOR=navy>E0</FONT> <TT>+</TT> <U><FONT COLOR=navy>E0</FONT></U></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>1)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E0</FONT> <TT>+</TT> <U><FONT COLOR=navy>E0</FONT></U> <TT>+</TT> <I>integer</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>etc.</TD>
</TR></TABLE><BR>
The expressions obtained by each derivation may look similar from the
point of view of expression evaluation:<BR><DIV ALIGN=center>
 (<I>integer</I> <TT>+</TT> <I>integer</I>) <TT>+</TT> <I>integer</I> and
 <I>integer</I> <TT>+</TT> (<I>integer</I> <TT>+</TT> <I>integer</I>)</DIV>
but different for building a syntax tree (see figure
<A HREF="book-ora058.html#fig-basic-ex1">6.3</A> on page <A HREF="book-ora058.html#fig-basic-ex1">??</A>).<BR>
<BR>
The second instance of a grammar generating a conflict between
shifting and reducing has the same type of ambiguity: an implicit
parenthesizing. But contrary to the previous case, the choice between
shifting and reducing modifies the meaning of the parsed
expression. Let's consider the following grammar:
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>E1</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><I>integer</I></TD>
<TD  ALIGN=right NOWRAP>(R1)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E1</FONT> <TT>+</TT> <FONT COLOR=navy>E1</FONT></TD>
<TD  ALIGN=right NOWRAP>(R2)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E1</FONT> <TT>*</TT> <FONT COLOR=navy>E1</FONT></TD>
<TD  ALIGN=right NOWRAP>(R3)</TD>
</TR></TABLE>
</DIV>
We find in this grammar the above-mentioned conflict both for <TT>+</TT>
and for <TT>*</TT>. But there is an added conflict between <TT>+</TT> and
<TT>*</TT>. Here again, an expression may be produced in two ways. There
are two right-hand derivations of <BR>
<BR>
<DIV ALIGN=center> <I>integer</I> <TT>+</TT> <I>integer</I> <TT>*</TT> <I>integer</I></DIV><BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP>First way:</TD>
<TD  ALIGN=right NOWRAP><FONT COLOR=navy>E1</FONT></TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>3)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E1</FONT> <TT>*</TT> <U><FONT COLOR=navy>E1</FONT></U></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>1)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><U><FONT COLOR=navy>E1</FONT></U> <TT>*</TT> <I>integer</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>2)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E1</FONT> <TT>+</TT> <U><FONT COLOR=navy>E1</FONT></U> <TT>*</TT> <I>integer</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>etc.</TD>
</TR></TABLE><BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP>Second way:</TD>
<TD  ALIGN=right NOWRAP><FONT COLOR=navy>E1</FONT></TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>2)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E1</FONT> <TT>+</TT> <U><FONT COLOR=navy>E1</FONT></U></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>3)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E1</FONT> <TT>+</TT> <FONT COLOR=navy>E1</FONT> <TT>*</TT> <U><FONT COLOR=navy>E1</FONT></U></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><FONT FACE=symbol>��</FONT><SUP><FONT SIZE=2>(<I>R</I>1)</FONT></SUP></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E1</FONT> <TT>+</TT> <U><FONT COLOR=navy>E1</FONT></U> <TT>*</TT> <I>integer</I></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>etc.</TD>
</TR></TABLE><BR>
Here both pairs of parenthesis (implicit) are not equivalent:<BR><DIV ALIGN=center> (<I>integer</I> <TT>+</TT> <I>integer</I>) <TT>*</TT> <I>integer</I>
 <FONT FACE=symbol>�</FONT> <I>integer</I> <TT>+</TT> (<I>integer</I> <TT>*</TT> <I>integer</I>)</DIV><BR>
This problem has already been cited for Basic expressions (see page
<A HREF="book-ora058.html#basic-synt0">??</A>). It was solved by attributing different
precedence to each operator: we reduce (R3) before (R2), which 
is equivalent to parenthesizing products.<BR>
<BR>
We can also solve the problem of choosing between <TT>+</TT> and <TT>*</TT>
by modifying the grammar. We introduce two new terminals: <FONT COLOR=navy>T</FONT>
(for terms), and <FONT COLOR=navy>F</FONT> (for factors), which gives:
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>E</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>E</FONT> <TT>+</TT> <FONT COLOR=navy>T</FONT></TD>
<TD  ALIGN=right NOWRAP>(R1)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>T</FONT></TD>
<TD  ALIGN=right NOWRAP>(R2)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>T</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>T</FONT> <TT>*</TT> <FONT COLOR=navy>F</FONT></TD>
<TD  ALIGN=right NOWRAP>(R3)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>F</FONT></TD>
<TD  ALIGN=right NOWRAP>(R4)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>F</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><I>integer</I></TD>
<TD  ALIGN=right NOWRAP>(R5)</TD>
</TR></TABLE>
</DIV>
There is now but a single way to reach the production sequence
<I>integer</I> <TT>+</TT> <I>integer</I>  <TT>*</TT> <I>integer</I>: using rule (R1).<BR>
<BR>
The third example concerns conditional instructions in programming
languages. A language such as Pascal offers two conditionals :
<TT>if .. then</TT> and <TT>if .. then .. else</TT>. Let's imagine the
following grammar:
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><FONT COLOR=navy>Instr</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><TT>if</TT> <FONT COLOR=navy>Exp</FONT> <TT>then</TT> <FONT COLOR=navy>Instr</FONT></TD>
<TD  ALIGN=right NOWRAP>(R1)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>if</TT> <FONT COLOR=navy>Exp</FONT> <TT>then</TT> <FONT COLOR=navy>Instr</FONT> <TT>else</TT> <FONT COLOR=navy>Instr</FONT></TD>
<TD  ALIGN=right NOWRAP>(R2)</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP>etc...</TD>
</TR></TABLE>
</DIV>
In the following situation:
<DIV ALIGN=center>
<TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD  ALIGN=center NOWRAP><FONT COLOR=navy>Action</FONT></TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Input</FONT></TD>
<TD  ALIGN=right NOWRAP><FONT COLOR=navy>Stack</FONT></TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>:</TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP><U><TT>else</TT></U>...</TD>
<TD  ALIGN=right NOWRAP>[<FONT COLOR=navy>Instr</FONT> <TT>then</TT> <FONT COLOR=navy>Exp</FONT> <TT>if</TT>...]</TD>
</TR>
<TR><TD  ALIGN=center NOWRAP>:</TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR></TABLE>
</DIV>
We cannot decide whether the first elements in the stack relate to
conditional (R1), in which case it must be reduced, or to the first
<FONT COLOR=navy>Instr</FONT> in rule (R2), in which case it must be shifted. <BR>
<BR>
Besides shift-reduce conflicts, bottom-up parsing may also generate
reduce-reduce conflicts.<BR>
<BR>
We now introduce the <TT>ocamlyacc</TT> tool which uses the bottom-up
parsing technique and may find these conflicts.<BR>
<BR>
<A NAME="toc140"></A>
<H3> The <TT>ocamlyacc</TT> Tool</H3>
<A NAME="sec-ocamlyacc"></A>
<A NAME="@concepts243"></A>
<A NAME="@fonctions359"></A>
The <TT>ocamlyacc</TT> tools is built with the same principles as <TT>ocamllex</TT>: it takes as input a file describing a grammar whose rules
 have semantic actions attached, and returns two Objective CAML files with
 extensions <TT>.ml</TT> ant <TT>.mli</TT> containing a parsing function
 and its interface.<BR>
<BR>

<H5> General format</H5><A NAME="yacc-format"></A>
<A NAME="@concepts244"></A>
The syntax description files for <TT>ocamlyacc</TT> use extension <TT>.mly</TT> by convention and they have the following structure:<BR>
<BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><TT>%{</TT></TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP>header</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><TT>}%</TT></TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP>declarations</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><TT>%%</TT></TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP>rules</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><TT>%%</TT></TD>
<TD  ALIGN=left NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=left NOWRAP>trailer-and-end</TD>
</TR></TABLE><BR>
The rule format is:<BR><TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP>non-terminal</TD>
<TD  ALIGN=center NOWRAP><TT>:</TT></TD>
<TD  ALIGN=left NOWRAP>symbol...symbol</TD>
<TD  ALIGN=left NOWRAP><TT>{</TT> semantic action <TT>}</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><TT>|</TT></TD>
<TD  ALIGN=left NOWRAP>...</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><TT>|</TT></TD>
<TD  ALIGN=left NOWRAP>symbol...symbol</TD>
<TD  ALIGN=left NOWRAP><TT>{</TT> semantic action <TT>}</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP><TT>;</TT></TD>
</TR></TABLE><BR>A symbol is either a terminal or a non-terminal. Sections ``header''
and ``trailer-and-end'' play the same role as in <TT>ocamllex</TT> with
the only exception that the header is only visible by the rules and
not by declarations. In particular, this implies that module openings
(<B>open</B>) are not taken into consideration in the declaration
part and the types must therefore be fully qualified.<BR>
<BR>

<H5> Semantic actions</H5>
Semantic actions are pieces of Objective CAML code executed when the parser
reduces the rule they are associated with. The body of a semantic
action may reference the components of the right-hand term of the
rule. These are numbered from left to right starting with 1. The first
component is referenced by <TT>$1</TT>, the second by <TT>$2</TT>, etc.<BR>
<BR>

<H5> Start Symbols</H5>
We may declare several start symbols in the grammar, by writing
in the declaration section:
<PRE>
 %start non-terminal .. non-terminal
</PRE>For each of them a parsing function will be generated. We must
precisely note, always in the declaration section, the
output type of these functions.
<PRE>
 %type &lt;output-type&gt; non-terminal
</PRE>The <CODE>output-type</CODE> must be qualified.<BR>
<BR>


<H3> Warning </H3> <HR>

Non-terminal symbols become the name of parsing functions. Therefore,
they must not start with a capital letter which is reserved for
constructors.


<HR>

<BR>
<BR>

<H5> Lexical units</H5>
<A NAME="@concepts245"></A>
Grammar rules make reference to lexical units, the terminals or
terminal symbols in the rules.<BR>
<BR>
One (or several) lexemes are declared in the following fashion:
<PRE>
 %token PLUS MINUS MULT DIV MOD
</PRE>Certain lexical units, like identifiers, represent a set of
(character) strings. When we find an identifier we may be interested
in recovering its character string. We specify in the parser that
these lexemes have an associated value by enclosing the type of this
value between <CODE>&lt;</CODE> and <CODE>&gt;</CODE>:
<PRE>
 %token &lt;string&gt; IDENT
</PRE>

<H3> Warning </H3> <HR>

After being processed by <TT>ocamlyacc</TT> all these declarations are
transformed into constructors of type <I>token</I>. Therefore,
they must start with a capital letter.


<HR>

<BR>
<BR>
We may use character strings as implicit terminals as in:
<PRE>
expr : expr "+" expr   { ... }
     | expr "*" expr   { ... }
     | ...             
     ;
</PRE>in which case it is pointless to declare a symbol which represents
them: they are directly processed by the parser without passing
through the lexer. In the interest of uniformity, we do not advise
this procedure.<BR>
<BR>

<H5> Precedence, associativity</H5>
<A NAME="@concepts246"></A>
<A NAME="@concepts247"></A>
<A NAME="@concepts248"></A>
We have seen that many bottom-up parsing conflicts arise from implicit
operator association rules or precedence conflicts between operators. To
handle these conflicts, we may declare default associativity
rules (left-to-right or non-associative) for operators as well as
precedence rules. The following declaration states that operators <TT>+</TT> (lexeme <TT>PLUS</TT>) and <TT>*</TT> (lexeme <TT>MULT</TT>) associate to
the right by default and <TT>*</TT> has a higher precedence than <TT>+</TT>
because <TT>MULT</TT> is declared after <TT>PLUS</TT>.
<PRE>
 %left PLUS
 %left MULT
</PRE>Two operators declared on the same line have the same precedence.<BR>
<BR>

<H5> Command options</H5> <TT>ocamlyacc</TT> has two options:
<UL>
<LI>
 <TT>-b name</TT>: the generated Objective CAML files are <TT>name.ml</TT>
and <TT>name.mli</TT>;

<LI> <TT>-v</TT>: create a file with extension <TT>.output</TT> contaning
rule numeration, the states in the automaton recognizing the grammar
and the sources of conflicts.
</UL>
<H5> Joint usage with <TT>ocamllex</TT></H5>
<A NAME="sec-join-alex"></A>
We may compose both tools <TT>ocamllex</TT> and <TT>ocamlyacc</TT> so that
the transformation of a character stream into a lexeme stream is the
input to the parser. To do this, type <I>lexeme</I> should be known
to both. This type is defined in the files with extensions <TT>.mli</TT>
and <TT>.ml</TT> generated by <TT>ocamlyacc</TT> from the declaration of
the <B>token</B>s in the matching file with extension <TT>.mly</TT>. The <TT>.mll</TT> file imports this type; <TT>ocamllex</TT>
translates this file into an Objective CAML function of type
<I>Lexing.lexbuf -&gt; lexeme</I>. The example on page
<A HREF="book-ora107.html#sec-basic-rev">??</A> illustrates this interaction and describes the
different phases of compilation.<BR>
<BR>
<A NAME="toc141"></A>
<H3> Contextual Grammars</H3>
<A NAME="@concepts249"></A>
<A NAME="@concepts250"></A>
<A NAME="@concepts251"></A>
Types generated by <TT>ocamlyacc</TT> process languages produced by
so-called context-free grammars. A parser for such a grammar
does not depend on previously processed syntactic values to process
the next lexeme. This is not the case of the language <I>L</I> described by
the following formula:<BR>
<BR>
<DIV ALIGN=center>
<I>L</I> ::= <I>wCw</I> | <I>w</I> with  <I>w</I> <FONT FACE=symbol>�</FONT> (<I>A</I>|<I>B</I>)<SUP><FONT SIZE=2>*</FONT></SUP>
</DIV>
where <I>A</I>, <I>B</I> and <I>C</I> are terminal symbols. We have written <I>wCw</I>
(with <I>w</I> <FONT FACE=symbol>�</FONT> (<I>A</I>|<I>B</I>)<SUP><FONT SIZE=2>*</FONT></SUP>) and not simply (<I>A</I>|<I>B</I>)<SUP><FONT SIZE=2>*</FONT></SUP><I>C</I>(<I>A</I>|<I>B</I>)<SUP><FONT SIZE=2>*</FONT></SUP> because we
want the <EM>same</EM> word to the left and right of the middle <I>C</I>.<BR>
<BR>
To parse the words in <I>L</I>, we must remember what has already
been found before letter <I>C</I> to verify that we find exactly the same
thing afterwards. Here is a solution for this problem based on
``visiting'' a stream. The general idea of the algorithm is to build a
stream parsing function which will recognize exactly the subword
before the possible occurrence of <I>C</I>.<BR>
<BR>
We use the type:


<PRE><BR># <B>type</B><CODE> </CODE>token<CODE> </CODE><CODE>=</CODE><CODE> </CODE>A<CODE> </CODE><CODE>|</CODE><CODE> </CODE>B<CODE> </CODE><CODE>|</CODE><CODE> </CODE>C<CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
Function <TT>parse_w1</TT> builds the memorizing function for the
first <I>w</I> under the guise of a list of atomic stream parsers
(i.e. for a single <I>token</I>):<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>parse_w1<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>s<CODE> </CODE><B>with</B><CODE> </CODE><B>parser</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE>'A;<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>parse_w1<CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><B>parser</B><CODE> </CODE><CODE>[&lt;</CODE>'A<CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"a"</CODE><TT>)</TT>::l<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE>'B;<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>parse_w1<CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><B>parser</B><CODE> </CODE><CODE>[&lt;</CODE>'B<CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"b"</CODE><TT>)</TT>::l<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>[]<CODE> </CODE>;;<BR><CODE>val parse_w1 : token Stream.t -&gt; (token Stream.t -&gt; string) list = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The result of the function returned by <TT>parse_w1</TT> is simply the
character string containing the parsed lexical unit.<BR>
<BR>
Function <TT>parse_w2</TT> takes as argument a list built by
<TT>parse_w1</TT> to compose each of its elements into a single
parsing function:


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>parse_w2<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>l<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>p::pl<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><B>parser</B><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>p;<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>parse_w2<CODE> </CODE>pl<TT>)</TT><CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>x<CODE>^</CODE>l<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><B>parser</B><CODE> </CODE><CODE>[&lt;&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>""</CODE><CODE> </CODE>;;<BR><CODE>val parse_w2 : ('a Stream.t -&gt; string) list -&gt; 'a Stream.t -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The result of applying <TT>parse_w2</TT> will be the string
representing subword <I>w</I>. By construction, function <TT>parse_w2</TT>
will not be able to recognize anything but the subword visited by
<TT>parse_w1</TT>.<BR>
<BR>
Using the ability to name intermediate results in streams, we
write the recognition function for the words in the language <I>L</I>:


<PRE><BR># <B>let</B><CODE> </CODE>parse_L<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>parser</B><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>parse_w1<CODE> </CODE>;<CODE> </CODE>'C;<CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>parse_w2<CODE> </CODE>l<TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>r<CODE> </CODE>;;<BR><CODE>val parse_L : token Stream.t -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Here are two small examples. The first results in the string
surrounding <I>C</I>, the second fails because the words surrounding <I>C</I>
are different:


<PRE><BR># parse_L<CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'A;<CODE> </CODE>'B;<CODE> </CODE>'B;<CODE> </CODE>'C;<CODE> </CODE>'A;<CODE> </CODE>'B;<CODE> </CODE>'B<CODE> </CODE><CODE>&gt;]</CODE>;;<BR><CODE>- : string = "abb"</CODE><BR># parse_L<CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'A;<CODE> </CODE>'B;<CODE> </CODE>'C;<CODE> </CODE>'B;<CODE> </CODE>'A<CODE> </CODE><CODE>&gt;]</CODE>;;<BR><CODE>Uncaught exception: Stream.Error("")</CODE><BR>

</PRE>
<BR>
<BR>
<HR>
<A HREF="book-ora105.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora107.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
